package com.lw.leetcode.arr.b;

/**
 * arr
 * b
 * 2428. 沙漏的最大总和
 */
public class MaxSum {

    public static void main(String[] args) {
        MaxSum test = new MaxSum();

        // 30
        int[][] grid = {{6, 2, 1, 3}, {4, 2, 1, 5}, {9, 2, 8, 7}, {4, 1, 2, 99}};

        // 35
//        int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        int i = test.maxSum(grid);
        System.out.println(i);
    }

    public int maxSum(int[][] grid) {
        int sum = 0;
        int max = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 2; i < m; i++) {
            sum = grid[i - 2][0] + grid[i - 2][1] + grid[i - 2][2] + grid[i - 1][1]
                    + grid[i][0] + grid[i][1] + grid[i][2];
            max = Math.max(max, sum);
            for (int j = 3; j < n; j++) {
                sum -= (grid[i - 2][j - 3] + grid[i - 1][j - 2] + grid[i][j - 3]);
                sum += (grid[i - 2][j] + grid[i - 1][j - 1] + grid[i][j]);
                max = Math.max(max, sum);
            }
        }
        return max;
    }

}
